package com.cheung.leetcode.backtrack;

import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * @BelongsProject : java-leetcode
 * @BelongsPackage : com.cheung.leetcode.backtrack
 * @Author :  cheungming
 * @CreateTime : 2024-05-28 15:24:49
 * @Description : 重新安排行程
 * @Version : 1.0
 */
public class Code332Test {

    Map<String, PriorityQueue<String>> map = new HashMap<>();
    List<String> itinerary = new LinkedList<>();

    public List<String> findItinerary(List<List<String>> tickets) {
        for (List<String> ticket : tickets) {
            String src = ticket.get(0), dst = ticket.get(1);
            if (!map.containsKey(src)) {
                map.put(src, new PriorityQueue<>());
            }
            map.get(src).offer(dst);
        }
        dfs("JFK");
        Collections.reverse(itinerary);
        return itinerary;
    }

    public void dfs(String curr) {
        while (map.containsKey(curr) && !map.get(curr).isEmpty()) {
            String tmp = map.get(curr).poll();
            dfs(tmp);
        }
        itinerary.add(curr);
    }


    @Test
    public void test1() {
        List<List<String>> tickets = List.of(List.of("MUC", "LHR"), List.of("JFK", "MUC"), List.of("SFO", "SJC"), List.of("LHR", "SFO"));
        assert findItinerary(tickets).equals(List.of("JFK", "MUC", "LHR", "SFO", "SJC"));
    }

    @Test
    public void test2() {
        List<List<String>> tickets = List.of(List.of("JFK", "SFO"), List.of("JFK", "ATL"), List.of("SFO", "ATL"), List.of("ATL", "JFK"), List.of("ATL", "SFO"));
        assert findItinerary(tickets).equals(List.of("JFK", "ATL", "JFK", "SFO", "ATL", "SFO"));
    }
}
